package arithmetic.tree;

/**
 *
 *   演示树的网站：http://cs.usfca.edu/~galles/visualization/
 *
 *  1. 二叉树：二叉树是每个节点最多有两个子树的树结构；
 *
 *  2. 完全二叉树：除最后一层外，每一层的节点达到最大数；除最后一层右边的节点缺少若干节点（满二叉树就是除最后一层都有最大节点数）；
 *
 *  3. 满二叉树：除最后一层外，每一层上的所有结点都有两个子结点；满二叉树是一种特殊的完全二叉树；
 *
 *  4. 二叉搜索树（BST树）：二叉树中，每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。又叫二叉搜索树。（二叉排序树），如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找，但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；
 *          性质一: 所有非叶子结点至多拥有两个儿子（Left和Right）；
 *          性质二: 所有结点存储一个关键字；
 *          性质三：非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
 *
 *  5. 平衡二叉树（AVL）：是二叉搜索树的一个进化体，为了解决BST树高度不均，导致树变成了链表，平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
 *
 *  6. 红黑树（rbtree）：红黑树是特殊的平衡二叉树（它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。），优点就是树到叶子节点深度一致，查找的效率也就一样，为logN.在实行查找，插入，删除的效率都一致
 *         性质1. 结点是红色或黑色。
 *         性质2. 根结点是黑色。
 *         性质3. 所有叶子都是黑色。（叶子是NIL结点）
 *         性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
 *         性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。
 *
 *
 *  7.B 树：既B-树：是一种平衡多路搜索树（并不是二叉的）：
 *          1.任意非叶子结点最多只有M个儿子；且M>2；
 *          2.根结点的儿子数为[2, M]；注：M阶代表一个树节点最多有多少个查找路径，当M=2则是2叉树,M=3则是3叉）；
 *          3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
 *          4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
 *          5.非叶子结点的关键字个数=指向儿子的指针个数-1；
 *          6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
 *          7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
 *          8.所有叶子结点位于同一层；
 *
 *     B-树特征：
 *           1.关键字集合分布在整颗树中；
 *           2.任何一个关键字出现且只出现在一个结点中；
 *           3.搜索有可能在非叶子结点结束；
 *           4.其搜索性能等价于在关键字全集内做一次二分查找；
 *           5.自动层次控制；
 *
 *
 *  8.B+树：B+树是B-树的变体，也是一种多路搜索树：
 *      B+的特性：
 *        1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
 *        2.不可能在非叶子结点命中；
 *        3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
 *        4.更适合文件索引系统；相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。
 *
 *        特点
 *             1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
 *             2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
 *             3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
               4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
               5、B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
 */
public class Tree {
}
